﻿//#include <iostream>
//#include <vector>
//using namespace std;
//
//// 定义全局变量
//int numProcesses, numResources; // 进程数和资源种类数
//vector<int> Available;          // 当前可用资源
//vector<vector<int>> Max;        // 每个进程的最大需求
//vector<vector<int>> Allocation; // 已分配资源
//vector<vector<int>> Need;       // 尚需资源
//
//// 安全性检查函数
//bool isSafe() 
//{
//    vector<int> Work = Available;   // 可用资源向量
//    vector<bool> Finish(numProcesses, false); // 记录进程是否完成
//    vector<int> safeSequence;       // 安全序列
//
//    for (int count = 0; count < numProcesses; ++count) 
//    {
//        bool found = false;
//        for (int i = 0; i < numProcesses; ++i) 
//        {
//            if (!Finish[i]) 
//            {
//                bool canAllocate = true;
//                for (int j = 0; j < numResources; ++j) 
//                {
//                    if (Need[i][j] > Work[j]) // 当前资源不足
//                    { 
//                        canAllocate = false;
//                        break;
//                    }
//                }
//                if (canAllocate) // 假设分配资源
//                {
//                    for (int j = 0; j < numResources; ++j) {
//                        Work[j] += Allocation[i][j];
//                    }
//                    safeSequence.push_back(i); // 记录进程顺序
//                    Finish[i] = true;          // 标记完成
//                    found = true;
//                }
//            }
//        }
//        if (!found)  // 如果找不到可以分配的进程
//        {
//            cout << "系统处于不安全状态！" << endl;
//            return false;
//        }
//    }
//
//    cout << "系统处于安全状态，安全序列为：";
//    for (int i : safeSequence) 
//    {
//        cout << "P" << i << " ";
//    }
//    cout << endl;
//    return true;
//}
//
//// 资源请求函数
//void requestResource(int processID, vector<int> request) 
//{
//    cout << "进程 P" << processID << " 请求资源：";
//    for (int r : request) 
//    {
//        cout << r << " ";
//    }
//    cout << endl;
//
//    // 检查请求是否合法
//    for (int i = 0; i < numResources; ++i) 
//    {
//        if (request[i] > Need[processID][i]) 
//        {
//            cout << "请求超过进程的最大需求！" << endl;
//            return;
//        }
//        if (request[i] > Available[i]) 
//        {
//            cout << "请求超过系统当前可用资源！" << endl;
//            return;
//        }
//    }
//
//    // 假设分配资源
//    for (int i = 0; i < numResources; ++i)
//    {
//        Available[i] -= request[i];
//        Allocation[processID][i] += request[i];
//        Need[processID][i] -= request[i];
//    }
//
//    // 安全性检查
//    if (isSafe()) 
//    {
//        cout << "资源分配成功！" << endl;
//    }
//    else 
//    {
//        // 回滚资源分配
//        cout << "分配后系统处于不安全状态，拒绝分配！" << endl;
//        for (int i = 0; i < numResources; ++i) {
//            Available[i] += request[i];
//            Allocation[processID][i] -= request[i];
//            Need[processID][i] += request[i];
//        }
//    }
//}
//
//int main() 
//{
//    // 输入系统资源信息
//    cout << "请输入进程数和资源种类数: ";
//    cin >> numProcesses >> numResources;
//
//    Available.resize(numResources);
//    Max.resize(numProcesses, vector<int>(numResources));
//    Allocation.resize(numProcesses, vector<int>(numResources, 0));
//    Need.resize(numProcesses, vector<int>(numResources));
//
//    cout << "请输入系统可用资源向量: ";
//    for (int i = 0; i < numResources; ++i) 
//    {
//        cin >> Available[i];
//    }
//
//    cout << "请输入每个进程的最大需求矩阵: " << endl;
//    for (int i = 0; i < numProcesses; ++i) 
//    {
//        for (int j = 0; j < numResources; ++j)
//        {
//            cin >> Max[i][j];
//            Need[i][j] = Max[i][j]; // 初始化Need矩阵
//        }
//    }
//
//    // 模拟资源请求
//    while (true) 
//    {
//        int processID;
//        vector<int> request(numResources);
//
//        cout << "\n请输入请求资源的进程ID (-1退出): ";
//        cin >> processID;
//        if (processID == -1) break;
//
//        cout << "请输入请求资源向量: ";
//        for (int i = 0; i < numResources; ++i) {
//            cin >> request[i];
//        }
//
//        requestResource(processID, request);
//    }
//
//    return 0;
//}


//#include <iostream>
//#include <vector>
//#include <algorithm>
//using namespace std;
//
//vector<int> Resource;//m种资源的总量
//vector<int> Available;//未分配的各种可用资源数量,总资源数减去allocation占有的资源数
//vector<vector<int>> claim;//最大需求矩阵
//vector<vector<int>> allocation;//分配矩阵
//vector<vector<int>> need;//需求矩阵
//int n,m;//n表示进程数，m表示资源种类
//void init()//初始化资源
//{
//	cout << "请输入资源种类数m以及进程数量：";
//	cin >> m >> n;
//	Resource.resize(m);
//	cout << "请输入m种资源的总量：";
//	for (int i = 0; i < m; i++)
//	{
//		cin >> Resource[i];
//	}
//	Available = Resource;//最开始非分配的可用资源总量等于资源总量，因为占有资源为0
//	allocation.resize(n , vector<int>(m,0));//初始化占用资源为0
//	need.resize(n, vector<int>(m));
//	cout << "请输入m种资源的最大需求矩阵：" << endl;
//	claim.resize(n, vector<int>(m));
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//		{
//			cin >> claim[i][j];
//			need[i][j] = claim[i][j] - allocation[i][j];//最开始需求矩阵等于最大需求
//		}
//	}
//}
//bool isSafeDfs(vector<int> work,vector<int>& safeSeq,vector<bool>& vis)
//{
//	if (safeSeq.size() == n)
//	{
//		return true;
//	}
//	for (int i = 0; i < n; i++)//第i个进程
//	{
//		if (!vis[i])
//		{
//			bool isenough = true;//资源是否足够的标志符
//			for (int j = 0; j < m; j++)
//			{
//				if (need[i][j] > work[j])
//				{
//					isenough = false;//资源不够
//					break;
//				}
//			}
//			if (isenough)
//			{
//				vector<int> newWork = work;
//				for (int j = 0; j < m; j++)
//				{
//					newWork[j] += allocation[i][j];
//				}
//				vis[i] = true;
//				safeSeq.emplace_back(i);
//				if (isSafeDfs(newWork, safeSeq, vis))
//				{
//					return true;
//				}
//				vis[i] = false;
//				safeSeq.pop_back();
//			}
//		}
//	}
//	return false;
//}
//void Requestsource()
//{
//	int pid;
//	cout << "请输入请求资源的进程号pid：";
//	cin >> pid;
//	cout << endl;
//	cout << "请输入请求不同资源的个数：";
//	vector<int> request(m);
//	for (int i = 0; i < request.size(); i++)
//		cin >> request[i];
//	//检查当前需求是否合法，需求合法需要request < available && request < need
//	for (int i = 0; i < m; i++)
//	{
//		if (request[i] > need[pid][i])
//		{
//			cout << "当前请求资源超过了最大需求,请求失败" << endl;
//			cout << "i：" << i << "，request[i]：" << request[i] << "，need[pid][i]：" << need[pid][i] << endl;
//			return; 
//		}
//		if (request[i] > Available[i])
//		{
//			cout << "资源不足，请求失败" << endl;
//			return;
//		}
//	}
//	//试探性分配（保存原始状态）
//	vector<int> copyAvailable = Available;
//	vector<vector<int>> copyNeed = need;
//	vector<vector<int>> copyAllocation = allocation;
//	//到这里请求资源是允许的，重新调整矩阵，need - request,available - request,allocation + request
//	for (int i = 0; i < request.size(); i++)
//	{
//		need[pid][i] -= request[i];
//		Available[i] -= request[i];
//		allocation[pid][i] += request[i];
//	}
//	//安全性检查
//	vector<int> work = Available;//可用资源
//	vector<int> safeSeq;//安全序列
//	vector<bool> vis(n, false);//初始化访问数组，表示进程是否被使用过
//	if (isSafeDfs(work,safeSeq,vis))
//	{
//		cout << "分配成功，安全序列为：" << endl;
//		for (int i = 0; i < safeSeq.size(); i++)
//			cout << "p" << safeSeq[i] << " ";
//		cout << endl;
//	}
//	else
//	{
//		cout << "不能满足需求，恢复原状态,阻塞进程" << endl;
//		Available = copyAvailable;
//		need = copyNeed;
//		allocation = copyAllocation;
//	}
//}
//void show()
//{
//	cout << "当前非分配资源数量Available：" << endl;
//	for (int i = 0; i < m; i++)
//	{
//		cout << Available[i] << " ";
//	}
//	cout << endl;
//	cout << "当前分配矩阵allocation：" << endl;
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//			cout << allocation[i][j] << " ";
//		cout << endl;
//	}
//	cout << "当前需求矩阵need：" << endl;
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j < m; j++)
//			cout << need[i][j] << " ";
//		cout << endl;
//	}
//}
//
//int main()
//{
//	init();
//	int f = 1;
//	while (true)
//	{
//		cout << "1：申请资源" << endl;
//		cout << "2：查看当前资源情况" << endl;
//		cout << "3：退出" << endl;
//		cout << "请输入你的操作：";
//		int a;
//		cin >> a;
//		switch (a)
//		{
//		case 1:
//			Requestsource();
//			break;
//		case 2:
//			show();
//			break;
//		case 3:
//			f = 0;
//			break;
//		default:
//			break;
//		}
//		if (f == 0)
//			break;
//	}
//	return 0;
//}

//3 2
//3 1 1 
//1 1 1
//4 2 2
//1
//1
//2 1 1
//剩余资源 1 0 0 


//#include <iostream>
//#include <vector>
//#include <iomanip>
//using namespace std;
//
//class BankerAlgorithm {
//private:
//    int n;  // 进程数
//    int m;  // 资源种类数
//    vector<int> available;  // 可用资源向量
//    vector<vector<int>> maxMatrix;  // 最大需求矩阵
//    vector<vector<int>> allocation;  // 分配矩阵（初始全为0）
//    vector<vector<int>> need;  // 需求矩阵（Need = Max - Allocation）
//
//public:
//    // 初始化函数
//    void initialize() {
//        cout << "请输入资源种类数m: ";
//        cin >> m;
//        cout << "请输入进程数n: ";
//        cin >> n;
//
//        // 初始化资源总量
//        available.resize(m);
//        cout << "请输入" << m << "种资源的总量: ";
//        for (int i = 0; i < m; i++) {
//            cin >> available[i];
//        }
//
//        // 初始化最大需求矩阵
//        maxMatrix.resize(n, vector<int>(m));
//        cout << "请输入" << n << "个进程对" << m << "种资源的最大需求:\n";
//        for (int i = 0; i < n; i++) {
//            for (int j = 0; j < m; j++) {
//                cin >> maxMatrix[i][j];
//            }
//        }
//
//        // 初始化分配矩阵（全为0）
//        allocation.resize(n, vector<int>(m, 0));
//
//        // 计算需求矩阵（Need = Max）
//        need = maxMatrix;  // 因Allocation为0，Need直接等于Max
//    }
//
//    // 获取进程数（新增方法）
//    int getProcessCount() const {
//        return n;
//    }
//
//    // 获取资源种类数（新增方法）
//    int getResourceCount() const {
//        return m;
//    }
//
//    // 安全性检查算法
//    bool isSafe(vector<int>& work, vector<bool>& finish, vector<int>& safeSeq) {
//        int count = 0;
//        bool found;
//
//        while (count < n) {
//            found = false;
//            for (int i = 0; i < n; i++) {
//                if (!finish[i]) {
//                    bool canAllocate = true;
//                    // 检查资源是否足够
//                    for (int j = 0; j < m; j++) {
//                        if (need[i][j] > work[j]) {
//                            canAllocate = false;
//                            break;
//                        }
//                    }
//
//                    // 找到可分配的进程
//                    if (canAllocate) {
//                        // 模拟进程运行完成
//                        for (int j = 0; j < m; j++) {
//                            work[j] += allocation[i][j];  // 回收资源
//                        }
//                        finish[i] = true;
//                        safeSeq[count] = i;  // 加入安全序列
//                        count++;
//                        found = true;
//                    }
//                }
//            }
//            // 未找到可分配进程则退出
//            if (!found) break;
//        }
//
//        // 检查是否所有进程都完成
//        return (count == n);
//    }
//
//    // 处理资源请求
//    bool requestResources(int pid, vector<int> request) {
//        // 步骤1：检查请求合法性
//        for (int i = 0; i < m; i++) {
//            // 请求超过需求
//            if (request[i] > need[pid][i]) {
//                cout << "错误：请求超过进程最大需求\n";
//                return false;
//            }
//            // 请求超过可用资源
//            if (request[i] > available[i]) {
//                cout << "资源不足，进程需等待\n";
//                return false;
//            }
//        }
//
//        // 步骤2：试探性分配
//        for (int i = 0; i < m; i++) {
//            available[i] -= request[i];
//            allocation[pid][i] += request[i];
//            need[pid][i] -= request[i];
//        }
//
//        // 步骤3：安全性检查
//        vector<int> work = available;  // 工作向量
//        vector<bool> finish(n, false);  // 完成标记
//        vector<int> safeSeq(n, -1);  // 安全序列
//
//        bool safe = isSafe(work, finish, safeSeq);
//
//        if (safe) {
//            cout << "分配成功! 安全序列: ";
//            for (int i = 0; i < n; i++) {
//                cout << "P" << safeSeq[i];
//                if (i != n - 1) cout << " → ";
//            }
//            cout << endl;
//            return true;
//        }
//        else {
//            // 步骤4：不安全则回滚分配
//            for (int i = 0; i < m; i++) {
//                available[i] += request[i];
//                allocation[pid][i] -= request[i];
//                need[pid][i] += request[i];
//            }
//            cout << "⚠️ 系统将进入不安全状态，已回滚分配\n";
//            return false;
//        }
//    }
//
//    // 打印当前状态
//    void printState() {
//        cout << "\n当前系统状态:\n";
//        cout << "进程\tMax\t\tAllocation\tNeed\t\tAvailable\n";
//        for (int i = 0; i < n; i++) {
//            cout << "P" << i << "\t";
//            // 打印Max
//            for (int j = 0; j < m; j++)
//                cout << maxMatrix[i][j] << " ";
//            cout << "\t\t";
//
//            // 打印Allocation
//            for (int j = 0; j < m; j++)
//                cout << allocation[i][j] << " ";
//            cout << "\t\t";
//
//            // 打印Need
//            for (int j = 0; j < m; j++)
//                cout << need[i][j] << " ";
//            cout << "\t\t";
//
//            // 打印Available（仅第一行）
//            if (i == 0) {
//                for (int j = 0; j < m; j++)
//                    cout << available[j] << " ";
//            }
//            cout << endl;
//        }
//    }
//};
//
//int main() {
//    BankerAlgorithm banker;
//    banker.initialize();  // 初始化系统
//
//    int choice;
//    do {
//        cout << "\n===== 银行家算法菜单 =====";
//        cout << "\n1: 申请资源\n2: 查看当前状态\n3: 退出\n请选择操作: ";
//        cin >> choice;
//
//        switch (choice) {
//        case 1: {
//            int pid;
//            vector<int> request;
//            // 使用新增的getProcessCount()方法
//            cout << "请输入请求资源的进程号 (0-" << banker.getProcessCount() - 1 << "): ";
//            cin >> pid;
//
//            // 使用新增的getResourceCount()方法
//            request.resize(banker.getResourceCount());
//            cout << "请输入" << banker.getResourceCount() << "种资源的请求数量: ";
//            for (int i = 0; i < banker.getResourceCount(); i++) {
//                cin >> request[i];
//            }
//
//            banker.requestResources(pid, request);
//            break;
//        }
//        case 2:
//            banker.printState();
//            break;
//        case 3:
//            cout << "程序已退出\n";
//            break;
//        default:
//            cout << "无效选择!\n";
//        }
//    } while (choice != 3);
//
//    return 0;
//}